package com.egghiro.framework.j2se.game.model.shape;

import java.util.Iterator;
import java.util.LinkedList;

public class Polygon2D {

    private LinkedList points = new LinkedList();

    public Polygon2D(Point2D[] pts) {
        if (polygonClock(pts)) {
            for (int i = 0; i < pts.length; i++) {
                this.points.add(pts[i]);
            }
        } else {
            for (int i = pts.length - 1; i >= 0; i--) {
                this.points.add(pts[i]);
            }
        }
    }

    public Triangle[] getTriangles() {

        float x1;
        float y1;
        float x2;
        float y2;
        float x3;
        float y3;

        LinkedList triangles = new LinkedList();

        boolean finish = false;

        if (this.points.size() == 3) {

            x1 = ((Point2D) points.get(0)).x;
            y1 = ((Point2D) points.get(0)).y;
            x2 = ((Point2D) points.get(1)).x;
            y2 = ((Point2D) points.get(1)).y;
            x3 = ((Point2D) points.get(2)).x;
            y3 = ((Point2D) points.get(2)).y;

            triangles.add(new Triangle(x1, y1, x2, y2, x3, y3));

            finish = true;
        }
        for (; !finish;) {

            int pointIndex = 0;
            boolean earFound = false;
            this.matchPoints();

            while (pointIndex < this.points.size()) {
                if (isEar((Point2D) this.points.get(pointIndex), pointIndex)) {
                    earFound = true;
                    break;
                }
                pointIndex++;
            }
            if (!earFound) {
                throw new RuntimeException("Cannot triangle polygon !");
            }

            Point2D p0 = this.getPreviousPoint(pointIndex);
            Point2D p1 = (Point2D) points.get(pointIndex);
            Point2D p2 = this.getNextPoint(pointIndex);

            x1 = p0.x;
            y1 = p0.y;
            x2 = p1.x;
            y2 = p1.y;
            x3 = p2.x;
            y3 = p2.y;

            triangles.add(new Triangle(x1, y1, x2, y2, x3, y3));

            this.points.remove(pointIndex);

            if (this.points.size() == 3) {

                x1 = ((Point2D) points.get(0)).x;
                y1 = ((Point2D) points.get(0)).y;
                x2 = ((Point2D) points.get(1)).x;
                y2 = ((Point2D) points.get(1)).y;
                x3 = ((Point2D) points.get(2)).x;
                y3 = ((Point2D) points.get(2)).y;

                triangles.add(new Triangle(x1, y1, x2, y2, x3, y3));

                finish = true;
            }
        }

        int size = triangles.size();
        Triangle[] result = new Triangle[size];
        for (int i = 0; i < size; i++) {
            result[i] = (Triangle) triangles.get(i);
        }

        return result;
    }

    private boolean isEar(Point2D point, int index) {

        if (point.type == Point2D.POINT_CONCAVE) {
            return false;
        }

        Point2D p0 = this.getPreviousPoint(index);
        Point2D p1 = (Point2D) points.get(index);
        Point2D p2 = this.getNextPoint(index);

        int numPoints = this.points.size();
        for (int i = 0; i < numPoints; i++) {

            Point2D currPoint = (Point2D) points.get(i);

            if (currPoint.equals(p0) || currPoint.equals(p1) || currPoint.equals(p2)) {
                continue;
            }

            if (currPoint.type == Point2D.POINT_CONCAVE) {
                if (this.isSide(currPoint, p0, p1, p2) && this.isSide(currPoint, p1, p0, p2)
                        && this.isSide(currPoint, p2, p0, p1)) {
                    return false;
                }
            }
        }
        return true;
    }

    public boolean isSide(Point2D p1, Point2D p2, Point2D a, Point2D b) {

        double dotProduct = 0.0;
        double crossProduct1 = 0.0;
        double crossProduct2 = 0.0;
        double a1, a2, b1, b2;

        a1 = (b.x - a.x);
        a2 = (b.y - a.y);
        b1 = (p1.x - a.x);
        b2 = (p1.y - a.y);
        crossProduct1 = a1 * b2 - a2 * b1;

        a1 = (b.x - a.x);
        a2 = (b.y - a.y);
        b1 = (p2.x - a.x);
        b2 = (p2.y - a.y);
        crossProduct2 = a1 * b2 - a2 * b1;

        dotProduct = crossProduct1 * crossProduct2;

        if (dotProduct >= 0) {
            return true;
        } else {
            return false;
        }
    }

    public void matchPoints() {

        int numPoints = this.points.size();
        for (int i = 0; i < numPoints; i++) {

            Point2D p1 = this.getPreviousPoint(i);
            Point2D p2 = (Point2D) points.get(i);
            Point2D p3 = this.getNextPoint(i);

            if (!convex(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y)) {
                ((Point2D) points.get(i)).type = Point2D.POINT_CONVEX;
            } else {
                ((Point2D) points.get(i)).type = Point2D.POINT_CONCAVE;
            }
        }
    }

    private boolean convex(double x1, double y1, double x2, double y2, double x3, double y3) {
        if (triangleArea(x1, y1, x2, y2, x3, y3) < 0) {
            return true;
        } else {
            return false;
        }
    }

    private double triangleArea(double x1, double y1, double x2, double y2, double x3, double y3) {
        double areaSum = 0;
        areaSum += x1 * (y3 - y2);
        areaSum += x2 * (y1 - y3);
        areaSum += x3 * (y2 - y1);
        return areaSum / 2;
    }

    private boolean polygonClock(Point2D[] pts) {

        int numPoints = pts.length;

        if (numPoints < 3) {
            throw new RuntimeException("Less than three points !");
        }
        Point2D minPoint = pts[0];
        int minIndex = 0;

        for (int i = 1; i < numPoints; i++) {

            Point2D curr = pts[i];

            if (curr.x > minPoint.x) {

                minPoint = curr;
                minIndex = i;
            } else if (curr.x == minPoint.x && curr.y < minPoint.y) {

                minPoint = curr;
                minIndex = i;
            }
        }

        Point2D p1 = null, p2 = null, p3 = null;

        if (minIndex == 0) {
            p1 = pts[numPoints - 1];
            p2 = pts[0];
            p3 = pts[1];
        } else if (minIndex == numPoints - 1) {
            p1 = pts[numPoints - 2];
            p2 = pts[numPoints - 1];
            p3 = pts[0];

        } else if (minIndex > 0 && minIndex < numPoints - 1) {
            p1 = pts[minIndex - 1];
            p2 = pts[minIndex];
            p3 = pts[minIndex + 1];
        }

        double crossProduct = (p2.x - p1.x) * (p3.y - p2.y);
        crossProduct = crossProduct - ((p2.y - p1.y) * (p3.x - p2.x));

        if (crossProduct < 0) {
            return true;
        } else {
            return false;
        }
    }

    private Point2D getNextPoint(int index) {
        if (index != this.points.size() - 1) {
            return (Point2D) points.get(index + 1);
        } else {
            return (Point2D) points.get(0);
        }
    }

    private Point2D getPreviousPoint(int index) {
        if (index != 0) {
            return (Point2D) points.get(index - 1);
        } else {
            return (Point2D) points.get(this.points.size() - 1);
        }
    }

    public Point2D findCentroid() {
        float cx = 0.0f, cy = 0.0f, f = 0;
        Iterator it = this.points.iterator();
        while (it.hasNext()) {
            Point2D p1 = (Point2D) it.next();
            if (!it.hasNext()) {
                break;
            }
            Point2D p2 = (Point2D) it.next();
            f = p1.x * p2.y - p2.x * p1.y;
            cx += (p1.x + p2.y) * f;
            cy += (p1.y + p2.y) * f;
        }
        cx = 1 / (6 * Math.abs(signedArea())) * cx;
        cy = 1 / (6 * Math.abs(signedArea())) * cy;
        return new Point2D(cx, cy);
    }

    private float signedArea() {
        float sum = 0.0f;
        Iterator it = this.points.iterator();
        while (it.hasNext()) {
            Point2D p1 = (Point2D) it.next();
            if (!it.hasNext()) {
                break;
            }
            Point2D p2 = (Point2D) it.next();
            sum += (p1.x * p2.y - p2.x * p1.y);
        }
        return 0.5f * sum;
    }

}
